/****************************************************************************
*																			*
*	File:		arraylist.h													*
*																			*
*	Author:		Robb T. Koether												*
*																			*
*	Date:		Jul 3, 2000													*
*																			*
*	Abstract:	This file contains the definition of the ArrayList 			*
*				template class												*
*																			*
****************************************************************************/

#ifndef ARRAYLIST_H
#define ARRAYLIST_H

//	Header files

#include <iostream>
#include <string>
#include <cassert>

using namespace std;

/****************************************************************************
*																			*
*	The ArrayList class definition											*
*																			*
****************************************************************************/

template <class T>
class ArrayList
{
//	Public member functions

	public:

	//	Constructors

		ArrayList(int sz = 0, const T& value = T());
		ArrayList(const ArrayList<T>& lst);
	
	//	Destructor
	
		~ArrayList() {delete [] element;}

	//	Inspectors

		T& GetElement(int pos) const
			{assert(pos >= 1 && pos <= size); return element[pos - 1];}
		int Size() const {return size;}
		bool Empty() const {return size == 0;}

	//	Mutators

		void SetElement(int pos, const T& value) {GetElement(pos) = value;}
		void Insert(int pos, const T& value);
		void Delete(int pos);
		void PushFront(const T& value) {Insert(1, value);}
		void PushBack(const T& value) {Insert(size + 1, value);}
		T PopFront() {T value = GetElement(1); Delete(1); return value;}
		T PopBack() {T value = GetElement(size); Delete(size); return value;}
		void MakeEmpty()
			{delete [] element; capacity = 0; size = 0; element = NULL;}

	//	Facilitators
	
		void Input(istream& in);
		void Output(ostream& out) const;
	
	//	Operators
	
		ArrayList<T>& operator=(const ArrayList<T>& lst);
		T& operator[](int pos) const {return GetElement(pos);}

	//	Other functions
	
		void Swap(ArrayList<T>& lst);
		int Search(const T& value) const;
		void Sort() {Sort(0, size - 1);}
		void Validate() const;

//	Protected member functions

	protected:
		void SetCapacity(int newCap);
		void MakeCopy(const ArrayList<T>& lst);
		
//	Private member functions

	private:
		void Sort(int left, int right);

//	Data members

	protected:
		int capacity;	// Allocated space
		int size;		// Number of items in list
		T* element;		// Pointer to first item
};

//	ArrayList operators

template <class T>
istream& operator>>(istream& in, ArrayList<T>& lst);
template <class T>
ostream& operator<<(ostream& out, const ArrayList<T>& lst);

/****************************************************************************
*																			*
*	Function:	ArrayList(int = 0, T& = T())								*
*																			*
*	Purpose:	This function will construct a list of the specified size	*
*																			*
****************************************************************************/

template <class T>
ArrayList<T>::ArrayList(int sz, const T& value)
{
	assert(sz >= 0);
	
	capacity = sz;
	size = sz;

	if (size == 0)
		element = NULL;
	else
		element = new T[capacity];

	for (int i = 0; i < size; i++)
		element[i] = value;
	return;
}

/****************************************************************************
*																			*
*	Function:	ArrayList(ArrayList&)										*
*																			*
*	Purpose:	This function will construct a list that is a copy of 		*
*				the specified list											*
*																			*
****************************************************************************/

template <class T>
ArrayList<T>::ArrayList(const ArrayList<T>& lst)
{
	MakeCopy(lst);
	return;
}

/****************************************************************************
*																			*
*	Function:	Insert														*
*																			*
*	Purpose:	This function will insert an element into the list at the	*
*				specified position											*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Insert(int pos, const T& value)
{
	assert(pos >= 1 && pos <= size + 1);
	
	if (size == capacity)
		if (capacity == 0)
			SetCapacity(1);
		else
			SetCapacity(2 * capacity);
	
	for (int i = size; i >= pos; i--)
		element[i] = element[i - 1];
	
	element[pos - 1] = value;
	size++;
	return;
}

/****************************************************************************
*																			*
*	Function:	Delete														*
*																			*
*	Purpose:	This function will delete the element in the specified 		*
*				position													*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Delete(int pos)
{
	assert(pos >= 1 && pos <= size);

	for (int i = pos; i < size; i++)
		element[i - 1] = element[i];

	size--;

	if (size <= capacity/4)
		SetCapacity(capacity/2);
	
	return;
}

/****************************************************************************
*																			*
*	Function:	Input														*
*																			*
*	Purpose:	This function will extract a list from the input stream		*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Input(istream& in)
{
	MakeEmpty();			// Clear out old values
	char c;
	T value;
	
	in >> c;				// Read the first character
	assert(c == '{');		// Verify it is open brace
	
	in >> c;				// Read next character
	if (c == '}')			// List is empty
		return;				// Nothing else to read
		
	else					// List is not empty
	{
		in.putback(c);		// Put char back in input stream
		while(c != '}')		// Read until '}' is found
		{
			in >> value;	// Read the element
		 	PushBack(value);// Append the element to the list
		 	in >> c;		// Read the comma or close brace
		}
	}
	return;
}

/****************************************************************************
*																			*
*	Function:	Output														*
*																			*
*	Purpose:	This function will insert a list into the output stream		*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Output(ostream& out) const
{
	out << "{";							// Write open brace
	if (size > 0)
	{
		for (int i = 0; i < size; i++)
			out << element[i] << ", ";	// Write element and comma
		out << "\b\b";					// Erase last comma
	}
	out << "}";							// Write close brace
	return;
}

/****************************************************************************
*																			*
*	Function:	operator=													*
*																			*
*	Purpose:	This function will assign one list to another				*
*																			*
****************************************************************************/

template <class T>
ArrayList<T>& ArrayList<T>::operator=(const ArrayList<T>& lst)
{
	if (this != &lst)						// Lists are distinct
	{
		delete [] element;					// Clear out old elements
		MakeCopy(lst);
	}
	return *this;
}

/****************************************************************************
*																			*
*	Function:	Swap														*
*																			*
*	Purpose:	This function will swap this list with the specified list	*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Swap(ArrayList<T>& lst)
{

//	Perform a swap of the three data members, not the allocated memory

	int tempMaxSize = lst.capacity;
	int tempSize = lst.size;
	T* tempElement = lst.element;

	lst.capacity = capacity;
	lst.size = size;
	lst.element = element;

	capacity = tempMaxSize;
	size = tempSize;
	element = tempElement;
	return;
}

/****************************************************************************
*																			*
*	Function:	Search(T)													*
*																			*
*	Purpose:	This function will use a sequential search to search the 	*
*				unsorted list for the specified element and report its 		*
*				location													*
*																			*
*	Note:		If the element was not found, the function returns 0		*
*																			*
****************************************************************************/

template <class T>
int ArrayList<T>::Search(const T& value) const 
{
	int pos;
	for (pos = 0; pos < size; pos++)
		if (element[pos] == value)
			return pos + 1;
	return 0;
}

/****************************************************************************
*																			*
*	Function:	Sort(int, int)												*
*																			*
*	Purpose:	This function will use the quicksort algorithm to sort 		*
*				the list recursively										*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Sort(int left, int right)
{
	if (left < right)
	{
		T temp;		// Used to swap list elements
		
	//	Pivot
	
		if (element[right] < element[left])
		{
			temp = element[right];
			element[right] = element[left];
			element[left] = temp;
		}
	
	//	Partition the list
	
		T pivot = element[left];
		int i = left;
		int j = right + 1;
		do
		{
			do ++i; while (element[i] < pivot);
			do --j; while (pivot < element[j]);
			if (i < j)
			{
				temp = element[i];
				element[i] = element[j];
				element[j] = temp;
			}
		} while (i < j);
		temp = element[j];
		element[j] = element[left];
		element[left] = temp;
		
	//	Sort the sublists recursively
	
		Sort(left, j - 1);
		Sort(j + 1, right);
	}
	return;
}

/****************************************************************************
*																			*
*	Function:	Validate													*
*																			*
*	Purpose:	To validate that the arraylist has a valid structure		*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::Validate() const
{
	assert(capacity >= 0);
	assert(size >= 0 && size <= capacity);
	
	if (capacity == 0)
		assert(element == NULL);
	else
		assert(element != NULL);
	
	return;
}

/****************************************************************************
*																			*
*	Function:	SetCapacity													*
*																			*
*	Purpose:	This function will reset the maximum size of the list to 	*
*				the specified size											*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::SetCapacity(int newCap)
{
//	Verify that new capacity is valid

	assert(newCap >= 0);

	capacity = newCap;
	T* new_array;
	
//	Allocate memory and copy elements

	if (capacity == 0)
	{
		size = 0;
		new_array = NULL;
	}
	else
	{
	//	Allocate memory
	
		new_array = new T[capacity];
	
	//	Get new size
	
		size = min(capacity, size);
		
	//	Copy elements
	
		for (int i = 0; i < size; i++)
			new_array[i] = element[i];
	}

//	Delete old memory

	delete [] element;
	element = new_array;
	return;
}

/****************************************************************************
*																			*
*	Function:	MakeCopy													*
*																			*
*	Purpose:	This function will set this list equal to a copy of the 	*
*				specified list												*
*																			*
****************************************************************************/

template <class T>
void ArrayList<T>::MakeCopy(const ArrayList<T>& lst)
{
	capacity = lst.capacity;
	size = lst.size;

	if (capacity == 0)
		element = NULL;
	else
		element = new T[capacity];

	for (int i = 0; i < size; i++)
		element[i] = lst.element[i];
	
	return;
}

/****************************************************************************
*																			*
*	Function:	operator>>													*
*																			*
*	Purpose:	This function will extract a list from the input stream		*
*																			*
****************************************************************************/

template <class T>
istream& operator>>(istream& in, ArrayList<T>& lst)
{
	lst.Input(in);
	return in;
}

/****************************************************************************
*																			*
*	Function:	operator<<													*
*																			*
*	Purpose:	This function will insert a list into the output stream		*
*																			*
****************************************************************************/

template <class T>
ostream& operator<<(ostream& out, const ArrayList<T>& lst)
{
	lst.Output(out);
	return out;
}

#endif